package leecode

import "sort"

type RangeFreqQuery struct {
	hashMap map[int][]int //key为数组中的元素 , value为对应下标
}

func Constructor2080(arr []int) RangeFreqQuery {
	hashMap := make(map[int][]int)
	for index, num := range arr {
		hashMap[num] = append(hashMap[num], index)
	}
	return RangeFreqQuery{hashMap}
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
	l := sort.SearchInts(this.hashMap[value], left)
	r := sort.SearchInts(this.hashMap[value], right)
	return r - l
}
